1. Technical Field
The present invention generally relates to an algorithm for sorting bit sequences, and in particular to an algorithm for sorting bit sequences in linear complexity.
2. Related Art
In the current state of the art with respect to sorting words (i.e., integers, strings, etc.), the fastest known algorithms have an execution speed proportional to NW log NW (i.e., of order NW log NW), wherein NW denotes the number of words to be sorted. The well-known Quicksort algorithm is an in-place sort algorithm (i.e., the sorted items occupy the same storage as the original items) that uses a divide and conquer methodology. To solve a problem by divide and conquer on an original instance of a given size, the original instance is divided into two or more smaller instances; each of these smaller instances is recursively solved (i.e., similarly divided), and the resultant solutions are combined to produce a solution for the original instance. To implement divide and conquer, Quicksort picks an element from the array (the pivot), partitions the remaining elements into those greater than and less than this pivot, and recursively sorts the partitions. The execution speed of Quicksort is a function of the sort ordering that is present in the array of words to be sorted. For a totally random distribution of words to be sorted Quicksort's execution speed is proportional to NW log NW. In some cases in which the words to be sorted deviate from perfect randomness, the execution speed may deteriorate relative to NW log NW and is proportional to (NW)2 in the worst case.
Given, the enormous execution time devoted to sorting a large number of integers, strings, etc. for extensively used applications such as spreadsheets, database applications, etc., there is a need for a sort algorithm having an execution speed of order less than NW log NW.